package ferp.core.ai.tree2;

import android.os.Debug;
import ferp.core.card.Card;
import ferp.core.card.Deck;
import ferp.core.game.Game;
import ferp.core.game.Trick;
import ferp.core.log.Log;
import ferp.core.player.Hand;

import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.*;

/**
 * User: igorgok
 * Date: 1/8/12 12:41 PM
 */
public class Resolver
{
  // is resolver ready to serve requests
  public static boolean ready = false;

  public static synchronized void preallocate()
  {
    if (Node.pool.total() == 0)
    {
      Runtime r = Runtime.getRuntime();
      // do not use all the memory at once
      memory = r.maxMemory();
      // assume position/move ratio 1:7
      long nc = Math.round(Math.sqrt(memory)) * 6, mc = nc * 7;

      Log.debug(Log.TAG, "max memory: " + memory + ", preallocating " + nc + " nodes, " + mc + " moves");

      Node.pool.preallocate(nc);
      Move.pool.preallocate(mc);

      Log.debug(Log.TAG, "Resolver resources allocated successfully");
    }
    else
      Log.debug(Log.TAG, "Resolver resources already allocated");

    ready = true;
    Resolver.class.notify();
  }

  public static synchronized void initialize(int evaluator, int declarer, int starter, int trump, int[] hands10, byte talon0, byte talon1, boolean open, boolean rostov, int sets, int drop)
  {
    while (!ready)
      try
      {
        Log.debug(Log.TAG, "resolver is not ready yet");
        Resolver.class.wait();
      }
      catch (InterruptedException e)
      {
        /* do nothing */
      }

    // clear previously created tree
    for (Level l : levels)
      l.clear(null);

    Resolver.sets = sets;
    // initialize cancelled flag
    Resolver.cancelled = false;
    // store the evaluator
    Resolver.evaluator = Evaluator.evaluators[evaluator];
    // store the declarer
    Resolver.declarer.id = declarer;
    // store the starter
    Resolver.starter = starter;
    // store the trump
    Resolver.trump = Card.Suit.values()[trump];
    // store talon
    Resolver.talon[0] = talon0;
    Resolver.talon[1] = talon1;
    // store open game flag
    Resolver.open = open;
    // store Rostov flag
    Resolver.rostov = rostov;
    // clear statistics
    Resolver.time = 0;
    Resolver.processed = Resolver.identical = 0;
    // reset rounds counter
    Resolver.round = 0;
    // reset drop
    Resolver.drop.reset();
    // reset trash
    Resolver.trash = 0;

    // update declarer hand with guessed drop
    if (declarer != Game.NO_ID)
    {
      Resolver.declarer.cards12 = hands10[declarer] | Card.card(talon0).hash | Card.card(talon1).hash;
      // guess drop if not passing
      Resolver.drop.current = (drop == 0 ? Resolver.evaluator.guess(Resolver.declarer.id, Resolver.declarer.cards12, Resolver.trump, starter, 0, sets, 0) : drop);
      // apply the guessed drop
      hands10[declarer] = Resolver.declarer.cards12 & ~Resolver.drop.current;

      Log.debug(Log.TAG, (drop == 0 ? "guessed" : "real") + " declarer hand [" + Hand.dump(hands10[declarer]) + "] with drop: " + Hand.dump(Resolver.drop.current));
    }

    // recalculation data
    Resolver.recalculate.required = false;
    System.arraycopy(hands10, 0, Resolver.recalculate.hands, 0, Game.PLAYERS);
    // set timeout according to the game type
    Resolver.timeout = declarer == Game.NO_ID ? PASSING_TIMEOUT : TRICKING_TIMEOUT;

    // create root position and add it at the depth 0 list
    Resolver.position = Node.create(levels[round], (byte)starter, hands10);
  }

  public static synchronized void recalculateOnNextSolve(int trick)
  {
    recalculate.required = true;
    recalculate.trick = trick;
  }

  // returns time in seconds spent on solving
  public static synchronized int solve()
  {
    if (recalculate.required)
    {
      Log.debug(Log.TAG, "resetting tree before solve for standing game");

      // clear previously created tree
      for (Level l : levels)
        l.clear(null);

      open = false;
      round = 0;
      time = 0;
      processed = identical = 0;

      // create root position and add it at the depth 0 list
      Resolver.position = Node.create(levels[0], (byte)starter, recalculate.hands);

      if (recalculate.trick != 0)
        advance(0, recalculate.trick);

      // turn recalculation off
      recalculate.required = false;
    }

    // do nothing if there is no free memory
    refine();
    //  return 0;

    long start = System.currentTimeMillis();
    int highest = MAX_LEVEL;

    logSolveStart();

    //debug(true);

    // the main loop
    while (!cancelled && (Resolver.position.propagated & Score.COMPLETE) == 0 && Node.pool.in() > MIN_REQUIRED_NODES && Move.pool.in() > MIN_REQUIRED_MOVES)
    {
      for (int from = Resolver.round; from < MAX_LEVEL && Node.pool.in() > MIN_REQUIRED_NODES && Move.pool.in() > MIN_REQUIRED_MOVES && System.currentTimeMillis() - start < Resolver.timeout; /**/)
        for (Level current = levels[from]; current.round < MAX_LEVEL; current = levels[current.round + 1])
          if (current.pending.size() > 0)
            process(current);
          else
            // do not start from an empty level again
            if (from == current.round)
              ++from;

      // print out
      //for (Level current = levels[Resolver.depth]; current.depth < MAX_LEVEL; current = levels[current.depth + 1])
      //  logLevelInfo(current, status);

      logPoolState();

      // do we have to stop?
      boolean timeout = (System.currentTimeMillis() - start) > Resolver.timeout;
      // partially propagate score and store the highest level the score was propagated to
      highest = propagateScore(timeout);

      if (timeout)
        break;
    }

    // final score propagation if required
    //if (highest != round)
    //  propagateScore(true);

    long time = (System.currentTimeMillis() - start) / 1000;

    Resolver.time += time;

    logProcessingTime(time);
    logBestScore();

    return (int)time;
  }

  // get the best move for the current position
  public static synchronized byte getBestMove(int depth, int hand, int trick, int cardsInHand)
  {
    final Card c0 = Trick.card(trick, 0);
    final Card c1 = Trick.card(trick, 1);
    final int candidatesInHand = Hand.getMoveCandidates(cardsInHand, trick, trump);

    Log.debug(Log.TAG, "getting best move for hand " + hand + ", depth " + depth + ", trick " + Trick.dump(trick, Card.Suit.NONE));

    // remove invalid moves
    for (position.children.start(); position.children.hasNextEntry(); /**/)
    {
      Move m = position.children.nextEntry();
      Card c = Card.card(m.card(hand));
      boolean invalid = (c.hash & candidatesInHand) == 0;
      boolean mismatched = (c0 != null && (c0.compressed != m.c0 || (c1 != null && c1.compressed != m.c1)));

      if (invalid || mismatched)
      {
        // card is not in hand
        position.children.removeCurrentEntry();
        m.destroy();

        Log.debug(Log.TAG, invalid ? "removed invalid move " + c : "removed mismatched move " + m);
      }
    }

    // we may not guess the last card is in the real drop (human move)
    if (position.children.size() == 0)
    {
      int p0 = position.player;
      int p1 = Game.next(p0);
      int p2 = Game.next(p1);
      int player;

      if (c0 == null)
      {
        hands[p0] = cardsInHand;
        hands[p1] = position.hands[p1];
        hands[p2] = position.hands[p2];
        player = p0;
      }
      else
        if (c1 == null)
        {
          hands[p0] = Hand.remove(position.hands[p0], c0.hash);
          hands[p1] = cardsInHand;
          hands[p2] = position.hands[p2];
          player = p1;
        }
        else
        {
          hands[p0] = Hand.remove(position.hands[p0], c0.hash);
          hands[p1] = Hand.remove(position.hands[p1], c1.hash);
          hands[p2] = cardsInHand;
          player = p2;
        }

      return Card.card(evaluator.getSingleCandidate(candidatesInHand, hands, player, trick, trump, round, hand, declarer.id, open)).compressed;
    }

    // sort all available moves by score
    while (position.children.size() > 0)
    {
      Move m = getBestMove(hand, c0, c1);

      // move can be null if children have no scores
      if (m == null)
        m = position.children.first();

      //Log.debug(Log.TAG, "best #" + (index++) + ": " + Card.card(m.card(hand)) + ", " + Score.toString(Score.increment(m.node.propagated, m.node.winner)));

      position.children.remove(m);
      moves.addLast(m);
    }

    //debug(moves.size() == 0);

    seen.clear();
    // move sorted moves back to the position
    for (moves.start(); moves.hasNextEntry(); /**/)
    {
      Move m = moves.nextEntry();
      byte card = m.card(hand);

      moves.removeCurrentEntry();
      position.children.addLast(m);

      if (!seen.contains(card))
      {
        Log.debug(Log.TAG, "case #" + seen.size() + ": " + Card.card(card) + (depth == seen.size() || (depth > seen.size() && !moves.hasNextEntry()) ? "*" : "") + " " + Score.toString(m.node.propagated));
        seen.add(card);
      }
    }

    seen.toArray(sorted);

    return depth < seen.size() ? sorted[depth] : sorted[seen.size() - 1];
  }

  // best moves
  private static final LinkedList<Move> moves = new LinkedList<Move>(Move.class);
  private static final LinkedHashSet<Byte> seen = new LinkedHashSet<Byte>();
  private static final Byte[] sorted = new Byte[10];

  private static Move getBestMove(int hand, Card c0, Card c1)
  {
    final byte p0 = Resolver.position.player;
    final byte p1 = (byte)Game.next(p0);
    final byte p2 = (byte)Game.next(p1);

    short b0 = 0, b1 = 0, b2 = 0;
    Move result = null;

    LinkedList<Move> children = Resolver.position.children;

    children.start();

    switch (hand)
    {
      case 0: {
        for (Move current = children.nextEntry(), next = children.hasNextEntry() ? children.nextEntry() : null; current != null; current = next, next = children.hasNextEntry() ? children.nextEntry() : null)
        {
          Node child = current.node;

          if (child.propagated != 0)
          {
            short score = Score.increment(child.propagated, child.winner);

            if (b2 == 0 || evaluator.isBetter(score, b2, p2, declarer.id))
              b2 = score;
          }

          if (next != null && current.c0 == next.c0)
          {
            if (current.c1 != next.c1)
            {
              if (b2 != 0 && (b1 == 0 || evaluator.isBetter(b2, b1, p1, declarer.id)))
                b1 = b2;

              b2 = 0;
            }
          }
          else
          {
            if (b2 != 0 && (b1 == 0 || evaluator.isBetter(b2, b1, p1, declarer.id)))
              b1 = b2;

            if (b1 != 0 && (b0 == 0 || evaluator.isBetter(b1, b0, p0, declarer.id)))
            {
              b0 = b1;
              result = current;
            }

            b1 = b2 = 0;
          }
        }

        return result;
      }

      case 1: {
        // the condition (current.c0 == c0) should probably hold for all remaining children after advance()
        // removes all the others
        for (Move current = children.nextEntry(), next; current != null; current = next)
          if (current.c0 == c0.compressed)
          {
            Node child = current.node;

            for (next = null; children.hasNextEntry(); /**/)
            {
              Move m = children.nextEntry();

              if (m.c0 == c0.compressed)
              {
                next = m;
                break;
              }
            }

            short score = Score.increment(child.propagated, child.winner);

            if (b2 == 0 || evaluator.isBetter(score, b2, p2, declarer.id))
              b2 = score;

            if (next == null || current.c1 != next.c1)
            {
              if (b1 == 0 || evaluator.isBetter(b2, b1, p1, declarer.id))
              {
                b1 = b2;
                result = current;
              }

              b2 = 0;
            }
          }
          else
            next = children.hasNextEntry() ? children.nextEntry() : null;

        return result;
      }

      case 2: {
        while (children.hasNextEntry())
        {
          Move move = children.nextEntry();

          short score = Score.increment(move.node.propagated, move.node.winner);

          if (move.c0 == c0.compressed && move.c1 == c1.compressed && (b2 == 0 || evaluator.isBetter(score, b2, p2, declarer.id)))
          {
            b2 = score;
            result = move;
          }
        }

        return result;
      }
    }

    throw new AssertionError("invalid hand " + hand);
  }

/*
  private static byte verify(Move move, byte card, int hand, int trick, int cardsInHand)
  {
    Card c = Card.card(card);

    // check if the picked card is in the hand
    if ((cardsInHand & c.hash) != 0)
      return card;

    // card is not in the hand, it was dropped - delete this position
    position.children.remove(move);
    move.destroy();

    // and try to determine best move again (there must be more moves)
    if (position.children.size() > 0)
      return getBestMove(hand, trick, cardsInHand);

    Log.debug(Log.TAG, "all cards in drop, current cards in hand " + Hand.dump(cardsInHand) + ", returning " + Hand.dump(Hand.first(cardsInHand)));

    return Card.card(Hand.first(cardsInHand)).compressed;
  }
*/

  // get current best score for the current position
  public static synchronized short getBestScore()
  {
    return Resolver.position.propagated;
  }

  // go deeper to the next position as the game goes on removing unused ones
  public static synchronized void advance(int hand, int trick)
  {
    final Level current = levels[Resolver.round];
    final Card c0 = Trick.card(trick, 0);
    final int p1 = Game.next(Resolver.position.player);
    LinkedList<Move> children = Resolver.position.children;

    children.start();

    if (hand == 0)
    {
      boolean found = false;

      // track the trash
      trash |= c0.hash;

      // look for move starting with c0
      while (children.hasNextEntry())
      {
        Move move = children.nextEntry();

        if (move.c0 == c0.compressed)
          found = true;
        else
        {
          children.removeCurrentEntry();
          move.destroy();
        }
      }

      if (!found)
      {
        // check the guessed drop
        checkGuessedDrop(c0, Resolver.position.player, trick);
        // no move found - create the (c0, x, y) branches
        process(current, Resolver.position, p1, trick, c0);
        // reset current propagated score (particularly, if it's complete next solve will not do anything)
        resetRootPosition(current);
      }

      return;
    }

    final Card c1 = Trick.card(trick, 1);
    final int p2 = Game.next(p1);

    if (hand == 1)
    {
      boolean found = false;

      // update the trash
      trash |= c1.hash;

      // look for move starting with c0 and c1
      while (children.hasNextEntry())
      {
        Move move = children.nextEntry();

        if (move.c0 == c0.compressed && move.c1 == c1.compressed)
          found = true;
        else
        {
          children.removeCurrentEntry();
          move.destroy();
        }
      }

      if (!found)
      {
        // check the guessed drop
        checkGuessedDrop(c1, p1, trick);
        // no move found - create the (c0, c1, x) branches
        process(current, Resolver.position, p2, trick, c0, c1);
        // reset current propagated score (particularly, if it's complete next solve will not do anything)
        resetRootPosition(current);
      }

      return;
    }

    final Card c2 = Trick.card(trick, 2);
    Node child = null;

    // update the trash
    trash |= c2.hash;

    // look for move with c0, c1 and c2
    while (children.hasNextEntry())
    {
      Move move = children.nextEntry();

      if (move.c0 == c0.compressed && move.c1 == c1.compressed && move.c2 == c2.compressed)
      {
        child = move.node;

        break;
      }
    }

    if (child == null)
    {
      // check the guessed drop
      checkGuessedDrop(c2, p2, trick);
      // no move found - create the (c0, c1, c2) branch
      // no need to reset root position here as it will be replaced with the "child"
      child = process(current, Resolver.position, trick, c0, c1, c2);
    }

    // the following should destroy the current position and decrease its children reference counters
    current.clear(null);
    // destroy all the nodes at the next level except the one we had found/created
    levels[Resolver.round + 1].clear(child);
    // this is the new tree root
    Resolver.position = child;
    // increase the depth
    ++Resolver.round;
  }

  private static void checkGuessedDrop(Card c, int player, int trick)
  {
    // for declarer only (NO_ID for ALL-PASS game
    if (player == declarer.id)
    {
      // save the current guessed drop
      int h = position.hands[player];

      // player moved card which is in guessed drop
      if ((c.hash & drop.current) != 0 || (c.hash & Hand.getMoveCandidates(h, Trick.pop(trick), trump)) == 0)
      {
        Log.debug(Log.TAG, "unexpected move: " + c + " -> " + ((c.hash & drop.current) != 0 ? "card in guessed drop" : ("card not in move candidates [" + Hand.dump(Hand.getMoveCandidates(h, Trick.pop(trick), trump)) + "]")));

        if (Hand.size(drop.guessed) >= 2)
          Log.debug(Log.TAG, "WARNING: drop has been guessed, but we got unexpected move");

        // c.hash is actually already in the trash, we do not need it there at this stage
        int mc12 = Hand.getMoveCandidates(Resolver.declarer.cards12 & ~trash | c.hash, Trick.pop(trick), trump);

        switch (Hand.size(mc12))
        {
          case 1:
            if (Trick.size(trick) > 1 && mc12 != c.hash)
            {
              // now we know 1 card
              Log.debug(Log.TAG, Hand.dump(mc12) + " is in the drop for sure");

              drop.guessed |= mc12;

              if (Hand.size(drop.guessed) < 2)
                drop.current = evaluator.guess(player, Resolver.declarer.cards12, Resolver.trump, starter, trash, sets, drop.guessed);
              else
              {
                drop.current = drop.guessed;

                Log.debug(Log.TAG, Hand.dump(drop.guessed) + " has been resolved as drop");
              }
            }
            else
              drop.current = evaluator.guess(player, Resolver.declarer.cards12, Resolver.trump, starter, trash, sets, drop.guessed);

            break;

          case 2:
            if (Trick.size(trick) > 1 && (mc12 & c.hash) == 0 && Hand.suits(mc12) == 1)
            {
              drop.guessed = drop.current = mc12;

              Log.debug(Log.TAG, Hand.dump(mc12) + " is the drop!");
            }
            else
              drop.current = evaluator.guess(player, Resolver.declarer.cards12, Resolver.trump, starter, trash, sets, drop.guessed);

            break;

          default:
            // new guessed drop
            drop.current = evaluator.guess(player, Resolver.declarer.cards12, Resolver.trump, starter, trash, sets, drop.guessed);
        }

        // change the hand by adding the old drop (incorrect) and removing the new one
        position.hands[player] = Resolver.declarer.cards12 & ~(drop.current | trash) | c.hash;

        Log.debug(Log.TAG, "new guessed hand [" + Hand.dump(position.hands[player]) + "], drop " + Hand.dump(drop.current));
/*
        // debug !!!
        if (Hand.size(position.hands[player]) != Hand.size(h))
          Log.debug(Log.TAG, "new player hand size differs from the old one");
*/
      }
    }
  }

  private static void resetRootPosition(Level current)
  {
    // reset propagated score
    Resolver.position.propagated = 0;

    // move root back from "complete" to "processed" list if required
    switch (current.complete.size())
    {
      case 0:
        break;

      case 1:
        Node n = current.complete.removeFirst();

        if (n != Resolver.position)
          throw new AssertionError("some other node (not root) is in the list of complete nodes");

        current.processed.addLast(Resolver.position);

        break;

      default:
        throw new AssertionError("list of completed nodes contains " + current.complete.size() + " objects");
    }
  }

  // cancel solve execution
  public static void cancel() {Resolver.cancelled = true;}

  public static synchronized long getAvailableMemory() {return memory;}
  public static synchronized int getNodePoolCapacity() {return Node.pool.total();}
  public static synchronized int getMovePoolCapacity() {return Move.pool.total();}
  // get resolving speed
  public static synchronized int getSpeed() {return time > 0 ? Math.round(processed / time) : 0;}

  private static final int PASSING_TIMEOUT  = 1500; // 1.5 seconds
  private static final int TRICKING_TIMEOUT = 3000; // 3 seconds

  private static final int MIN_REQUIRED_NODES = 100;
  private static final int MIN_REQUIRED_MOVES = 100;

  // max number of rounds to calculate
  private static final int TOTAL_ROUNDS = 10;
  // max level index
  private static final int MAX_LEVEL = TOTAL_ROUNDS;
  // max tree depth
  private static final int TOTAL_LEVELS = MAX_LEVEL + 1;

  private static final class Declarer
  {
    int id;
    int cards12;
  }

  private static final class Recalculate
  {
    boolean required;
    final int[] hands = new int[Game.PLAYERS];
    int trick;
  }

  private static final class Drop
  {
    int current;
    int guessed;

    void reset() {current = guessed = 0;}
  }

  // available memory
  private static long memory;
  // tree levels
  private static final Level[] levels = new Level[TOTAL_LEVELS];
  // evaluator
  private static Evaluator evaluator;
  // sets in game
  private static int sets;
  // game starter
  private static int starter;
  // game trump
  private static Card.Suit trump;
  // game declarer
  private static final Declarer declarer = new Declarer();
  // game talon
  private static byte[] talon = new byte[Game.TALON_SIZE];
  // current guessed drop
  private static final Drop drop = new Drop();
  // current trash - we can keep track of it in advance() method
  private static int trash;
  // is game flavor Rostov ?
  private static boolean rostov;
  // is open game?
  private static boolean open;
  // current position
  private static Node position;
  // current depth
  private static int round;
  // hands
  private final static int[] hands = new int[Game.PLAYERS];
  // cancelled flag
  private static boolean cancelled;
  // log buffer
  private static StringBuilder sb = new StringBuilder(512);
  // timeout
  private static int timeout;
  // statistics
  private static long time;
  private static long processed;
  private static long identical;
  // recalculate data
  private static final Recalculate recalculate = new Recalculate();

  static {
      // initialize levels
      for (int i = 0; i < levels.length; ++i)
        levels[i] = new Level(i);
  }

  private static void process(Level current)
  {
    // remove first pending node and process it
    Node node = current.pending.removeFirst();
    int trick = trick(current.round);
    // get candidates for next move
    int candidates = evaluator.getMoveCandidates(node.hands, node.player, trick, trump, current.round, 0, declarer.id, open);

    // create child positions
    for (int hash = evaluator.start(candidates); hash != 0; hash = evaluator.next(candidates, hash))
    {
      Card move = Card.card(hash);

      process(current, node, Game.next(node.player), Trick.add(trick, node.player, move.compressed), move);
    }

    // add to the processed list
    current.processed.addLast(node);
  }

  private static void process(Level current, Node parent, int nextPlayer, int trick, Card c0)
  {
    // get candidates for next move
    int candidates = evaluator.getMoveCandidates(parent.hands, nextPlayer, trick, trump, current.round, 1, declarer.id, open);

    // create child positions
    for (int hash = evaluator.start(candidates); hash != 0; hash = evaluator.next(candidates, hash))
    {
      Card move = Card.card(hash);

      process(current, parent, Game.next(nextPlayer), Trick.add(trick, nextPlayer, move.compressed), c0, move);
    }
  }

  private static void process(Level current, Node parent, int nextPlayer, int trick, Card c0, Card c1)
  {
    // get candidates for next move
    int candidates = evaluator.getMoveCandidates(parent.hands, nextPlayer, trick, trump, current.round, 2, declarer.id, open);

    // create child positions
    for (int hash = evaluator.start(candidates); hash != 0; hash = evaluator.next(candidates, hash))
    {
      Card move = Card.card(hash);

      process(current, parent, Trick.add(trick, nextPlayer, move.compressed), c0, c1, move);
    }
  }

  private static Node process(Level current, Node parent, int trick, Card c0, Card c1, Card c2)
  {
    // create new node
    Node node;
    Level deeper = levels[current.round + 1];
    byte winner = Trick.winner(trick, trump);
    boolean map = declarer.id != Game.NO_ID || current.round >= Game.TALON_SIZE || rostov;

    int p0 = parent.player;
    int p1 = Game.next(p0);
    int p2 = Game.next(p1);

    // remove played cards from hands
    hands[p0] = Hand.remove(parent.hands[p0], c0.hash);
    hands[p1] = Hand.remove(parent.hands[p1], c1.hash);
    hands[p2] = Hand.remove(parent.hands[p2], c2.hash);

    // do not look for duplicate sub-trees in initial passing rounds as there might be multiple winners
    if (map)
    {
      if ((node = Node.set.get(Node.key(winner, hands))) == null)
      {
        // position not found - create new one
        node = Node.create(deeper, parent, hands, winner, winner, c0, c1, c2);
        // store this position in the hash map
        Node.set.put(node);
      }
      else
      {
        // add existing node as a child and increment its number of parents
        parent.children.addLast(Move.create(c0, c1, c2, node));

        ++node.parents;
        ++Resolver.identical;
      }
    }
    else
      // set the correct starting player for the next round
      node = Node.create(deeper, parent, hands, (byte)starter, winner, c0, c1, c2);

    // collect processed nodes statistics
    ++Resolver.processed;

    return node;
  }

  private static int trick(int round)
  {
    // if passing game open a talon card before first hand plays
    return declarer.id == Game.NO_ID && !Resolver.rostov && round < Game.TALON_SIZE ? Trick.add(0, talon[round]) : 0;
  }

  // propagate score and perform pruning
  // return highest level where score was propagated
  private static int propagateScore(boolean finaL)
  {
    //debug(true);

    // initialize score at the bottom (all the nodes are in the "pending" list)
    for (levels[MAX_LEVEL].pending.start(); levels[MAX_LEVEL].pending.hasNextEntry();)
    {
      Node node = levels[MAX_LEVEL].pending.nextEntry();

      node.propagated = Score.COMPLETE;
    }

    // maxN algorithm - propagate score upwards starting from the level before last
    int d = MAX_LEVEL - 1;

    for (; d >= Resolver.round; d--)
    {
      //debug(d == 2);
      for (levels[d].processed.start(); levels[d].processed.hasNextEntry(); /**/)
      {
        Node node = levels[d].processed.nextEntry();

        if (node.children.size() > 0)
        {
          byte p0 = node.player;
          byte p1 = (byte)Game.next(p0);
          byte p2 = (byte)Game.next(p1);
          short b0 = 0, b1 = 0, b2 = 0, complete = Score.COMPLETE;
          LinkedList<Move> children = node.children;

          children.start();

          for (Move current = children.nextEntry(), next = children.hasNextEntry() ? children.nextEntry() : null; current != null; current = next, next = children.hasNextEntry() ? children.nextEntry() : null)
          {
            Node child = current.node;
            short score = 0;

            // update completeness flag - eventually will be set only if all the child scores are complete
            complete = (short)(complete & child.propagated);

            if (child.propagated != 0)
            {
              score = Score.increment(child.propagated, child.winner);

              if (b2 == 0 || evaluator.isBetter(score, b2, p2, declarer.id))
                b2 = score;
            }

            if (next != null && current.c0 == next.c0)
            {
              if (current.c1 != next.c1)
              {
                if (b2 != 0 && (b1 == 0 || evaluator.isBetter(b2, b1, p1, declarer.id)))
                  b1 = b2;

                b2 = 0;
              }
            }
            else
            {
              if (b2 != 0 && (b1 == 0 || evaluator.isBetter(b2, b1, p1, declarer.id)))
                b1 = b2;

              if (b1 != 0 && (b0 == 0 || evaluator.isBetter(b1, b0, p0, declarer.id)))
                b0 = b1;

              b1 = b2 = 0;
            }
          }

          // set the new best score considering computed completeness bit
          node.propagated = (short)(((b0 == 0 ? (b1 == 0 ? b2 : b1) : b0) & Score.SCORE) | complete);

          // prune weak moves only if the sub-tree is complete
          if (complete != 0)
          {
            // move this node to the "complete" list
            levels[d].processed.removeCurrentEntry();

            levels[d].complete.addLast(node);
            // we will refine the tree from the level next to this one
            //from = d;
          }
  /*
            for (Iterator<Move> mi = node.children.iterator(); mi.hasNext();)
            {
              Node child = mi.next().node;

              if (child != chosen)
              {
                // remove the node from child list
                mi.remove();
                // and dereference it, so the removeUnusedPosition will collect it
                if (--child.parents < 1)
                  ++pruned;
              }
            }
          }
  */
        }
      }
    }

/*
    if (pruned > 0)
    {
      logPruningResult(pruned);
      // remove pruned nodes
      if (!finaL)
        refine(from + 1);
    }
*/

    return d + 1;
  }

  private static int refine() {return refine(Resolver.round + 1);}
  private static int refine(int from)
  {
    int removed = 0;

    // walk down the tree
    for (int d = from; d < TOTAL_LEVELS; ++d)
    {
      Level level = levels[d];

      // now remove the unused nodes in both lists
      removed += refine(level.complete) + refine(level.processed) + refine(level.pending);
      //removed += refine(level.processed) + refine(level.pending);

      // clear scores in the list of processed nodes
      //for (Node n : level.processed)
      //  n.propagated = 0;
    }

    logRefineResult(removed, from);

    return removed;
  }

  private static int refine(LinkedList<Node> list)
  {
    int size = list.size();

    // now remove the unused nodes
    for (list.start(); list.hasNextEntry();)
    {
      Node n = list.nextEntry();

      if (n.parents == 0)
      {
        list.removeCurrentEntry();
        n.destroy();
      }
    }

    // how many nodes were removed
    return size - list.size();
  }

  private static void logSolveStart()
  {
    sb.setLength(0);

    sb.append("building tree from depth ").append(Resolver.round);

    Log.debug(Log.TAG, sb.toString());
  }

/*
  private static void logLevelInfo(Level level, Status status)
  {
    sb.setLength(0);

//    sb.append('@').append(depth).append(" - positions: processed=").append(level.processed.size()).append(", pending=")
//      .append(level.pending.size()).append(", added=").append(status.added).append(", identical=").append(status.identical);

    sb.append('@').append(level.depth).append(" - (").append(status.processed).append(',').append(status.pending1).append("), processed=")
      .append(level.processed.size() - status.processed).append(", added=").append(status.added).append(", identical=").append(status.identical);

    Log.d(TAG, sb.toString());
  }
*/

  private static void logProcessingTime(long time)
  {
    sb.setLength(0);

    sb.append("processing time ").append(time).append('s').append(", processed ").append(processed).append(", identical ").append(identical);

    Log.debug(Log.TAG, sb.toString());
  }

  private static void logPoolState()
  {
    sb.setLength(0);

    sb.append("pools state: node (").append(Node.pool.total()).append(',').append(Node.pool.in()).append("), move (")
      .append(Move.pool.total()).append(',').append(Move.pool.in()).append(')');

    Log.debug(Log.TAG, sb.toString());
  }

  private static void logBestScore()
  {
    sb.setLength(0);

    sb.append("best score for player ").append(Resolver.position.player).append(": ").append(Score.toString(Resolver.position.propagated));

    Log.debug(Log.TAG, sb.toString());
  }

/*
  private static void logValue(String message, int value)
  {
    sb.setLength(0);

    sb.append(message).append(value);

    Log.debug(Log.TAG, sb.toString());
  }

  private static void logPruningResult(int pruned)
  {
    logValue("nodes pruned ", pruned);
  }
*/

  private static void logRefineResult(int removed, int from)
  {
    sb.setLength(0);

    sb.append("nodes removed ").append(removed).append(" from level ").append(from);

    Log.debug(Log.TAG, sb.toString());

    logPoolState();
  }

  public static void debug(boolean when)
  {
    //if (!Config.PRODUCTION && when)
    if (when)
    {
      Log.debug(Log.TAG, "waiting for debugger...");
      Debug.waitForDebugger();
    }
  }

  // resolver test
  public static void main(String[] args) throws Exception
  {
    TestLog log = new TestLog();
    Deck deck = Deck.instance();
    int[] hands = new int[Game.PLAYERS];
    ArrayList<Integer> counts = new ArrayList<Integer>(Game.PLAYERS);
    ArrayList<Card> talon = new ArrayList<Card>(Game.TALON_SIZE);
    ArrayList<Card> cards = new ArrayList<Card>(12);
    double ratio = Double.MIN_VALUE;

    Resolver.preallocate();

    for (int i = 0; i < Game.PLAYERS; ++i)
      counts.add(0);

    for (int g = 0; true; ++g)
    {
      log.open();

      //int gameType = random.nextInt(Evaluator.TRICKING + 1);
      int gameType = Evaluator.TRICKING;
      int starter = random.nextInt(Game.PLAYERS);
      // simulate human play
      int declarer = gameType == Evaluator.PASSING ? Game.NO_ID : 0;
      //int declarer = gameType == Evaluator.PASSING ? Game.NO_ID : random.nextInt(Game.PLAYERS);
      Card.Suit trump = gameType == Evaluator.TRICKING ? Card.Suit.values()[random.nextInt(Card.Suit.values().length)] : Card.Suit.NONE;
      int drop = 0;

      talon.clear();
      cards.clear();
      deck.shuffle();

      // deal
      for (int i = 0, h = 0; i < Deck.SIZE - Game.TALON_SIZE; h = (h + 1) % Game.PLAYERS)
        for (int n = 0; n < 2; ++n, ++i)
        {
          Card c = deck.card(i);

          hands[h] = Hand.add(hands[h], c.hash);

          if (h == declarer)
            cards.add(c);
        }

      // remaining cards go to the talon
      for (int i = 0; i < Game.TALON_SIZE; ++i)
        talon.add(deck.card(Deck.SIZE - Game.TALON_SIZE + i));

      if (gameType != Evaluator.PASSING)
      {
        cards.addAll(talon);

        for (int i = 0; i < Game.TALON_SIZE; ++i)
          drop = Hand.add(drop, cards.remove(random.nextInt(cards.size())).hash);
      }

/*
      gameType = 0;
      declarer = 0; starter = 2; trump = Card.Suit.NONE;
      hands[0] = 171216922; hands[1] = 80299077; hands[2] = -251524320;
      talon.add(Card.card((byte)21)); talon.add(Card.card((byte)22));
      drop = 8320;
      int[] tricks = {-1063189913,-1073200762,-1070370425,-1063123864,-1073396829,-1072148078,-1070042476,-1070107499,-1070172777};
      //hands[declarer] = Hand.remove(Hand.add(hands[declarer], talon.get(0).hash | talon.get(1).hash), drop);
*/

      String gts = "ALL-PASS";

      switch (gameType)
      {
        case Evaluator.TRICKING: gts = "PLAY"  ; break;
        case Evaluator.MISERE  : gts = "MISERE"; break;
      }

      System.out.println("Starting game #" + g + ", type " + gts + (gameType != Evaluator.PASSING ? ", declarer " + declarer + ", trump " + trump : "") + ", first hand " + starter);
      System.out.println("hands: [" + hands[0] + "], [" + hands[1] + "], [" + hands[2] + "], talon: (" + talon.get(0).compressed + ", " + talon.get(1).compressed + ")");
      System.out.println("hands: [" + Hand.dump(hands[0]) + "], [" + Hand.dump(hands[1]) + "], [" + Hand.dump(hands[2]) + "]");
      System.out.println("talon: " + talon.get(0).toString() + ' ' + talon.get(1).toString());

      // initialize resolver before entering "moving mode"
      int[] hands10 = hands.clone();
      Resolver.initialize(gameType, declarer, starter, trump.ordinal(), hands10, talon.get(0).compressed, talon.get(1).compressed, true, false, g, 0);

      // do the real drop
      if (gameType != Evaluator.PASSING)
      {
        hands[declarer] = (hands[declarer] | talon.get(0).hash | talon.get(1).hash) & ~drop;
        System.out.println("drop: " + Hand.dump(drop) + " (" + drop + ")");
        System.out.println("real hands: [" + Hand.dump(hands[0]) + "], [" + Hand.dump(hands[1]) + "], [" + Hand.dump(hands[2]) + "]");
      }

      Collections.fill(counts, 0);

      for (int r = 0; r < 10; ++r)
      {
        int trick = trick(r);
        byte player = Resolver.position.player;

        // solve position
        solve();

        // update ratio
        ratio = Math.max((double)Move.pool.out() / Node.pool.out(), ratio);

        for (int h = 0; h < Game.PLAYERS; ++h)
        {
          // always return best move for testing purposes
          //getBestMove(10, h, trick, hands[player]);

          Card c = Card.card(player > 0 ? getBestMove(0, h, trick, hands[player]) : getRandomMove(hands, player, trick, trump, r, h, declarer, drop));
          //Card c = Card.restore(player > 0 ? getBestMove(h, trick, hands[player]) : getHumanMove(h, trick, hands[player], tricks));
          //Card c = Card.restore(getRecordedMove(tricks, round, h, player, trick, hands[player]));

          // put card to trick
          trick = Trick.add(trick, player, c.compressed);
          // advance resolver
          advance(h, trick);

          // verify guessed drop
          if (Resolver.drop.guessed != 0 && (drop & Resolver.drop.guessed) == 0)
          {
            System.out.println("Drop verification failed: guessed drop " + Hand.dump(Resolver.drop.guessed) + ", real drop " + Hand.dump(drop));
            return;
          }

          // remove played card from hand
          hands[player] = Hand.remove(hands[player], c.hash);

          player = (byte)Game.next(player);
        }

        System.out.println("#" + r + ":" + Trick.dump(trick, trump));

        byte winner = Trick.winner(trick, trump);
        counts.set(winner, counts.get(winner) + 1);
      }

      System.out.println("--- " + counts + " ----------------------------------------------------------------[" + ratio + ']');

      log.close();
    }
  }

  private static byte getRandomMove(int[] hands, int player, int trick, Card.Suit trump, int round, int hand, int declarer, int drop)
  {
    int candidates = Hand.getMoveCandidates(hands[player], trick, trump);
    Card card = null;

    for (int hash = Hand.first(candidates), n = random.nextInt(Hand.size(candidates)); n >= 0; hash = Hand.next(candidates, hash), --n)
      card = Card.card(hash);

    return card.compressed;

/*
    int candidates = evaluator.getMoveCandidates(hands, player, trick, trump, round, hand, declarer, true);
    int first = evaluator.start(candidates);
    int size = 0;
    Card card = null;

    for (int hash = first; hash != 0; hash = evaluator.next(candidates, hash))
      ++size;

    for (int hash = first, n = random.nextInt(size); n >= 0; hash = evaluator.next(candidates, hash), --n)
      card = Card.card(hash);

    return card.compressed;
*/
  }

  private static byte getHumanMove(int hand, int trick, int cardsInHand, int[] tricks)
  {
    Scanner scanner = new Scanner(System.in);

    System.out.println("moves: " + Trick.dump(trick, trump));
    System.out.println("cards in hand " + Hand.dump(cardsInHand));

    if (tricks.length > round)
      System.out.println("hint " + Trick.dump(tricks[round], trump));

    System.out.print("enter suit 0-3: ");
    Card.Suit s = Card.Suit.values()[scanner.nextInt()];

    System.out.print("\nenter rank 7-14: ");
    Card.Rank r = Card.Rank.values()[scanner.nextInt() - 7];

    return Card.card(s, r).compressed;
  }

  private static byte getRecordedMove(int[] tricks, int round, int hand, int player, int trick, int cardsInHand)
  {
    System.out.println("cards in hand " + Hand.dump(cardsInHand));

    if (tricks.length > round)
    {
      System.out.println("hint " + Trick.dump(tricks[round], trump));

      Card c = Trick.card(tricks[round], hand);

      if (c != null)
        return c.compressed;
    }

    System.out.println("no more recorded moves");

    //return player > 0 ? getBestMove(hand, trick, cardsInHand) : getHumanMove(hand, trick, cardsInHand, tricks);
    return getBestMove(0, hand, trick, cardsInHand);
  }

  private static class TestLog extends Log
  {
    public TestLog() throws Exception
    {
      parent = new File("D:\\Long run test");
      if (!parent.exists() && !parent.mkdir())
        throw new Exception("Failed to create log directory " + parent.getName());

      file = File.createTempFile("log", ".txt", parent);

      log = this;
    }

    @Override
    protected void d(String tag, String msg)
    {
      System.out.println(msg);

      try
      {
        if (msg.startsWith("working cells"))
          fos.write((msg + "\n").getBytes());
      }
      catch (IOException e)
      {
        e.printStackTrace();
      }
    }

    @Override
    protected void e(String tag, Throwable t)
    {
      close();

      t.printStackTrace();
      System.exit(-1);
    }

    public void open() throws Exception
    {
      fos = new FileOutputStream(file, true);
    }

    public void close()
    {
      try
      {
        fos.close();
      }
      catch (IOException e)
      {
        e.printStackTrace();
      }
    }

    private File parent;
    private File file;
    private FileOutputStream fos;
  }

  private static final Random random = new Random();
}
